/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

namespace LeetCode0981TimeBaseStore {

    interface TimeMapData {
        value: string,
        timestamp: number
    }

    class TimeMap {

        private map: Map<string, TimeMapData[]>;

        constructor() {
            this.map = new Map();
        }

        set(key: string, value: string, timestamp: number): void {
            if (this.map.has(key)) {
                // 检查输入是否合法(题设为递增输入)
                let ary: TimeMapData[] = this.map.get(key) as TimeMapData[];
                if (ary && ary.length > 0 && ary[ary.length - 1].timestamp < timestamp) {
                    ary.push({ value, timestamp });
                }
            } else {
                this.map.set(key, [{ value, timestamp }]);
            }
        }

        get(key: string, timestamp: number): string {
            // check empty
            if (!this.map || !this.map.has(key))
                return '';
            // check timestamp
            let ary: TimeMapData[] = this.map.get(key) as TimeMapData[];
            if (!ary || ary.length == 0 || ary[0].timestamp > timestamp)
                return "";
            // 二分查找
            let l0 = 0, l1 = ary.length - 1;
            while (l0 <= l1) {
                const half = Math.floor((l1 - l0) / 2) + l0;
                if (ary[half].timestamp > timestamp) {
                    l1 = half - 1;
                } else if (ary[half].timestamp < timestamp) {
                    l0 = half + 1;
                } else {
                    return ary[half].value;
                }
            }
            if (l1 >= 0)
                return ary[l1].value;
            return "";
        }
    }

}